package 剑指offer;

public class _25合并两个排序的链表 {
	public static void main(String[] args) {
		ListNode l1=new ListNode(1);
		l1.next=new ListNode(2);
		l1.next.next=new ListNode(4);
		
		ListNode l2=new ListNode(1);
		l2.next=new ListNode(3);
		l2.next.next=new ListNode(4);
		System.out.println(mergeTwoLists2(l1,l2));
	}
	/**
	 * 
	 *@time 2021年2月6日下午4:00:15
	 * 
	 *@param l1
	 *@param l2
	 *@return ListNode
	 *
	 *@see 代码更加繁琐
	 */
	 public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
         if(l1==null) return l2;
         if(l2==null) return l1;
         ListNode res=null;
         if(l1.val>=l2.val){
             res=new ListNode(l2.val);
             l2=l2.next;
         }
         else {
             res=new ListNode(l1.val);
             l1=l1.next;
         }
         ListNode p=res;
         while(l1!=null&&l2!=null){
             if(l1.val>=l2.val){
                 p.next=new ListNode(l2.val);
                 l2=l2.next;
             }else{
                p.next=new ListNode(l1.val);
                l1=l1.next;
             }
             p=p.next;
         }
         while(l1!=null){
             p.next=new ListNode(l1.val);
             p=p.next;
             l1=l1.next;
         }
           while(l2!=null){
             p.next=new ListNode(l2.val);
             p=p.next;
             l2=l2.next;
         }
         return res;
 }
	 /**
	  * 
	  *@time 2021年2月6日下午3:59:20
	  * 
	  *@param l1
	  *@param l2
	  *@return ListNode
	  *
	  *@seeKrahets的 代码更加的简洁
	  */
	 public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
		 ListNode res=new ListNode(0), p=res;
		 while(l1!=null&&l2!=null) {
			 if(l1.val<=l2.val) {
				p.next=l1;
				l1=l1.next;
			 }else {
				p.next=l2;
				l2=l2.next;
			}
			 p=p.next;
		 }
		 p.next= l1==null? l2:l1;
		return res.next; 
	 }
}
